package leetcode.sword;

public class Solution12 {
    public static void main(String[] args) {
        char[][] board = {{'A','B','C','C'},{'S','F','C','S'},{'A','D','E','E'}};
        int rowNum = board.length;
        int colNum = board[0].length;
        String word = "ABCF";
        int[][] forbidden = new int[rowNum][colNum];
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                if(findWordInBoard(board, i, j, word,0, forbidden)){
                    System.out.println(true);
                }
            }
        }
        System.out.println(false);
    }

    public static boolean findWordInBoard(char[][] board, int starti, int startj, String word, int wordi, int[][] forbidden){
        /**
         * 用于递归查找的函数，starti, startj是当前开始对比的board格子下标，wordi是当前要对比的word字符下标，forbidden记录禁忌搜索
         */
        if(starti<0 || starti>board.length-1 || startj<0 || startj>board[0].length-1){ //搜索到board边界了
            return false;
        }
        if(forbidden[starti][startj]==1){ //当前格子已被搜索过
            return false;
        }
        if(board[starti][startj]!=word.charAt(wordi)) {//当前格子和要查找的word元素不同
            return false;
        }else{//当前格子和要查找的word元素相同
            forbidden[starti][startj] = 1; //向附近查找前先把当前格子设为禁忌，防止回溯
            if (wordi == word.length()-1) { //word已被全部找到
                return true;
            }
            //word还没找齐，从当前格子向附近继续查找
            if (findWordInBoard(board, starti, startj - 1, word, wordi+1, forbidden)) {//向左把剩余的word找到了
                return true;
            }
            if (findWordInBoard(board, starti, startj + 1, word, wordi+1, forbidden)) {//向右把剩余的word找到了
                return true;
            }
            if (findWordInBoard(board, starti - 1, startj, word, wordi+1, forbidden)) {//向上把剩余的word找到了
                return true;
            }
            if (findWordInBoard(board, starti + 1, startj, word, wordi+1, forbidden)) {//向下把剩余的word找到了
                return true;
            }
            //上下左右都找不齐
            forbidden[starti][startj] = 0; //放开禁忌
            return false;
        }
    }
}